package a00_LeetCode.Tree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author quan
 * @Description 完全二叉树的节点个数
 * @Date 2023/3/31 14:42
 */
public class Num222_getNodeSum {
    /**
     * 方法1：递归法：确定终止条件：如果为空节点的话，就返回0，表示节点数为0。
     * 确定单层递归的逻辑：先求它的左子树的节点数量，再求右子树的节点数量，最后取总和再加一 （加1是因为算上当前中间节点）就是目前节点为根节点的节点数量。
     */
   /* public int getNodeSum(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftNum = getNodeSum(root.left);
        int rightNum = getNodeSum(root.right);
        return 1+leftNum+rightNum;
    }*/
    /**
     * 方法2：迭代法：层序遍历：加一个变量reuslt统计节点数量即可
     */
    public int getNodeSum(TreeNode root){
        if(root == null){
            return 0;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        int result = 0;
        while (!deque.isEmpty()){
            result++;
            TreeNode node = deque.pop();
            if(node.left!= null){
                deque.offer(node.left);
            }
            if(node.right != null){
                deque.offer(node.right);
            }
        }
        return result;
    }

}
